package com.zhanghp.class01.sort;

import static com.zhanghp.class01.sort.utils.SortUtils.*;

/**
 * 插入排序
 *
 * @author zhanghp
 * @date 2023-07-25 23:13
 */
public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = rand(20);
        printArr(arr);
//        reverseInsertSort(arr);
//        reverseInsertSortOptimize(arr);
//        forwardInsertSort(arr);
//        forwardInsertSortOptimize(arr);
        printArr(arr);
    }

    /**
     * 从左往右插
     * 插入顺序：左 -> 右
     * 数值顺序：小 -> 大
     *
     * @param arr 乱序数组
     */
    public static void reverseInsertSort(int[] arr) {
        // 边界条件
        if (arr == null || arr.length < BOUNDERY_LENGTH) {
            return;
        }
        // 0~1 1位置插入
        // 0~2 2位置插入
        for (int i = 0; i < arr.length; i++) {
            int cur = i;
            // 1.前一位索引下标是否在数组里
            // 2.当前索引和前一位索引的数值大小比较
            while ((cur - 1) >= 0 && (arr[cur - 1] > arr[cur])) {
                // 满足条件，交换
                swap(arr, cur, cur - 1);
                // 当前索引减1
                cur--;
            }
        }
    }

    /**
     * 正向插入排序
     * 插入顺序：右 -> 左
     * 数值顺序：小 -> 大
     *
     * @param arr 乱序数组
     */
    public static void forwardInsertSort(int[] arr) {
        if (arr == null || arr.length < BOUNDERY_LENGTH) {
            return;
        }
        // arr.length-2 ~ arr.length-1
        // arr.length-3 ~ arr.length-1
        for (int i = arr.length - 1; i >= 0; i--) {
            int cur = i;
            // 1.后一位索引下标是否在数组
            // 2.当前索引与后一位索引的数值大小比较
            while ((cur + 1 < arr.length) && arr[cur + 1] < arr[cur]) {
                swap(arr, cur, cur + 1);
                cur++;
            }
        }
    }

    /**
     * 逆向插入排序 - 优化
     * 插入顺序：左 -> 右
     * 数值顺序：小 -> 大
     *
     * @param arr 乱序数组
     */
    public static void reverseInsertSortOptimize(int[] arr) {
        if (arr == null || arr.length < BOUNDERY_LENGTH) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            // 1.前一位索引下标是否在数组里
            // 2.当前索引和前一位索引的数值大小比较
            // 当条件表达式2为false，说明该索引的值已在它该所属的位置，结束循环
            for (int cur = i; (cur - 1 >= 0) && (arr[cur - 1] > arr[cur]); cur--) {
                swap(arr, cur, cur - 1);
            }
        }
    }

    /**
     * 正向插入排序 - 优化
     * 插入顺序：右 -> 左
     * 数值顺序：小 -> 大
     *
     * @param arr 乱序数组
     */
    public static void forwardInsertSortOptimize(int[] arr) {
        if (arr == null || arr.length < BOUNDERY_LENGTH) {
            return;
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            // 1.后一位索引下标是否在数组
            // 2.当前索引与后一位索引的数值大小比较
            // 当条件表达式2为false，说明该索引的值已在它该所属的位置，结束循环
            for (int cur = i; (cur + 1 < arr.length) && (arr[cur + 1] < arr[cur]); cur++) {
                swap(arr, cur, cur + 1);
            }
        }
    }
}
